package aobing;

import java.util.*;

/**
 * Test
 *
 * @author Syzer
 * @Description 分割回文串2
 * @Date 2021/7/18 12:01
 */
public class PartitionPalindrome2 {
    public static List<String> wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        List<String>[] arr = new ArrayList[len + 1];
        arr[0] = new ArrayList<>();
        for(int i = 1;i <= len;i++) {
            for(int j = 0;j < i;j++) {
                String endsWith = s.substring(j, i);
                if(arr[j] != null && wordDict.contains(endsWith)) {
                    List<String> subArr = arr[i] != null ? arr[i] : new ArrayList<>();
                    if(j == 0) {
                        subArr.add(endsWith);
                    } else {
                        for(int k = 0;k < arr[j].size();k++) {
                            subArr.add(arr[j].get(k) + " " + endsWith);
                        }
                    }
                    arr[i] = subArr;
                }
            }
        }
        return arr[len] == null ? arr[0] : arr[len];
    }

    public static List<String> wordBreak1(String s, List<String> wordDict) {
        Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>();
        List<List<String>> wordBreaks = backtrack(s, s.length(), new HashSet<String>(wordDict), 0, map);
        List<String> breakList = new LinkedList<String>();
        for (List<String> wordBreak : wordBreaks) {
            breakList.add(String.join(" ", wordBreak));
        }
        return breakList;
    }

    public static List<List<String>> backtrack(String s, int length, Set<String> wordSet, int index, Map<Integer, List<List<String>>> map) {
        if (!map.containsKey(index)) {
            List<List<String>> wordBreaks = new LinkedList<List<String>>();
            if (index == length) {
                wordBreaks.add(new LinkedList<String>());
            }
            for (int i = index + 1; i <= length; i++) {
                String word = s.substring(index, i);
                if (wordSet.contains(word)) {
                    List<List<String>> nextWordBreaks = backtrack(s, length, wordSet, i, map);
                    for (List<String> nextWordBreak : nextWordBreaks) {
                        LinkedList<String> wordBreak = new LinkedList<String>(nextWordBreak);
                        wordBreak.offerFirst(word);
                        wordBreaks.add(wordBreak);
                    }
                }
            }
            map.put(index, wordBreaks);
        }
        return map.get(index);
    }

    public static void main(String[] args) {
//        "pineapplepenapple"
//                ["apple","pen","applepen","pine","pineapple"]
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("aa");
        list.add("aaa");
        list.add("aaaa");
        list.add("aaaaa");
        list.add("aaaaaa");
        list.add("aaaaaaa");
        list.add("aaaaaaaa");
        list.add("aaaaaaaaa");
        list.add("aaaaaaaaaa");
        List<String> list1 = wordBreak("aaaaaaaaaaaaaaaaaaaa", list);
        Set<String> set = new HashSet<>(list1);
        List<String> list2 = wordBreak1("aaaaaaaaaaaaaaaaaaaa", list);
        for(String str : list2) {
            set.remove(str);
        }
        System.out.println(list1.size() + "===" + list2.size());
        System.out.println(set);
    }
}
